The present invention concerns the design of a high-speed, multi-format multiplier, and a multiplier compiler which produces a schematic of the high-speed, multi-format multiplier.
In the design of integrated circuits, synthesis tools and silicon compilers are often used. Based on specifications received from a designer, the synthesis tools, or synthesizers, generate netlists, while the silicon compilers generate "hard" layout of the integrated circuits. Netlists are textual lists of components and connections. Hard layouts show how the components may implemented in silicon. The netlists, once generated, and the hard layout, once generated, are extremely difficult to modify.
Compilers written to produce hardware multipliers have used a variety of algorithms. The goal of each algorithm is to produce a hardware multiplier which has a high circuit density and/or has high performance. The ideal, yet hard to attain, multiplier compiler produces a hardware multiplier which combines high performance while taking up a minimum of space on an integrated circuit.
One solution has been to provide a multiplier compiler which automatically inserts pipeline registers. In one embodiment of such a multiplier compiler, a user specifies the performance rate at which a multiplier is to receive multipliers and multiplicands and produce a product. The multiplier compiler will then produce a multiplier which inserts as many pipeline stages as necessary so that the specified performance rate can be met.
While such a multiplier compiler does facilitate the inclusion of a multiplier in a system which operates at a high frequency, there is no actual performance gain through the multiplier. For example, a combinatorial multiplier with a propagation delay of 50 nanoseconds can be retrofitted to a system with a 30 nanosecond clock rate by the insertion of one pipeline stage. The resultant multiplier will require two 30 nanosecond cycles to complete a multiplication rather than one 50 nanosecond cycle. Thus the overall computational performance of the multiplier is not improved.
An ideal multiplier compiler not only has the flexibility to allow a user to make performance versus chip density trade-offs, but also allows a user flexibility to, in the design of a multiplier, select the format of the multiplier and multiplicand which will be multiplied by the multiplier. Common formats include signed magnitude, unsigned magnitude and two's complement.
Once a multiplier has been included on an integrated circuit that is mass produced, each fabricated integrated circuit is tested to assure that a customer receives working parts. The multiplier is typically tested by applying test vectors to the input of the multiplier, each test vector including a multiplier and a multiplicand. The product for each test vector received from the multiplier is strobed and compared against the correct answer. A product incorrectly calculated by the multiplier indicates flawed circuitry. An integrated circuit containing a multiplier with flawed circuitry is discarded.
One approach to thoroughly test a multiplier is to have a test vector for every combination of multiplier and multiplicand. However, for even moderate size multipliers the required amount of test vectors is impractically high. For example, using such a system, a multiplier which multiplied two eight bit numbers would require 65,536 test vectors. A multiplier which multiplied two ten bit numbers would require 1,048,546 test vectors. Such a large number of test vectors increases the time required to test an integrated circuit, and thus increases the expense of performing testing.
Sets of test vectors may be generated with fewer test vectors in each set, however, it is difficult for a designer of test vectors who is not intimately acquainted with the design of a multiplier to specify an efficient set of test vectors which will thoroughly test a multiplier.